package org.example.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liyishan
 * @date 2024/4/2 09:31
 * @apiNote
 */

public class Test00894AllPossibleFBT {

    public List<TreeNode> allPossibleFBT(int n) {
        List<TreeNode> fullBinaryTrees = new ArrayList<>();
        if (n % 2 == 0) {
            return fullBinaryTrees;
        }
        if (n == 1) {
            fullBinaryTrees.add(new TreeNode(0));
            return fullBinaryTrees;
        }
        for (int i = 1; i < n; i += 2) {
            List<TreeNode> leftTrees = allPossibleFBT(i);
            List<TreeNode> rightTrees = allPossibleFBT(n - 1 - i);
            for (TreeNode leftSubTree : leftTrees) {
                for (TreeNode rightSubTree : rightTrees) {
                    TreeNode root = new TreeNode(0, leftSubTree, rightSubTree);
                    fullBinaryTrees.add(root);
                }
            }
        }
        return fullBinaryTrees;
    }

    public List<TreeNode> allPossibleFBT1(int n) {
        if (n % 2 == 0) {
            return new ArrayList<>();
        }
        List<TreeNode>[] dp = new List[n + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = new ArrayList<>();
        }
        dp[1].add(new TreeNode(0));
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i; j += 2) {
                for (TreeNode left : dp[j]) {
                    for (TreeNode right : dp[i - 1 - j]) {
                        TreeNode root = new TreeNode(0, left, right);
                        dp[i].add(root);
                    }
                }
            }
        }
        return dp[n];
    }


}
